package com.company.Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}10:44
 */
public class PolandNotation {


    public static void main(String[] args) {
//        String suffixExpression = "30 4 + 5 x 6 -";
//        List<String> listString = getListString(suffixExpression);
//        int calculate = calculate(listString);
//        System.out.println(suffixExpression + "=" + calculate);
//

        /**
         * 中缀表达式转后缀表达式
         * 因为直接对str进行操作
         * 将字符串的List转成后缀表达式
         * @param
         */
        String expression = "10+((2+3)*4)-5";
        List<String> list = toInfixExpresssionList(expression);
        List<String> list1 = parseSuffiExpreesion(list);
        System.out.println();
        System.out.println(list1);
    }

    //将中缀表达式转成对应的List
    public static List<String> toInfixExpresssionList(String s) {
        //定义一个List,存放中缀表达式 对应的内容
        List<String> ls = new ArrayList<>();
        int i = 0;//这时是一个指针，用于遍历 中缀表达式字符串
        String str;//对多位数的拼接
        char c;// 每遍历一个字符，就放入到c
        do {
            //如果c是一非数字，需要加入到ls
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {//如果是数字要考虑多位数的问题
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }

    /**
     * 将后缀表达式转换为对应的中缀表达式
     */
    public static List<String> parseSuffiExpreesion(List<String> ls) {
        Stack<String> s1 = new Stack<>();//符号
//        Stack<String> s2 = new Stack<>();//存储中间结果  但是由于s2没有pop操作，因此比较麻烦，所以用List<String>代替栈
        List<String> s2 = new ArrayList<>();
        for (String s : ls) {
            if (s.matches("\\d+")) {
                s2.add(s);
            } else if (s.equals("(")) {
                s1.push(s);
            } else if (s.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将此小括号弹出 消除掉小括号
            } else {
                //缺少比较优先级高低的方法
                while (s1.size() != 0 && Operation.getOperation(s1.peek()) >= Operation.getOperation(s)) {
                    s2.add(s1.pop());
                }
                s1.push(s);
            }
        }

        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }


    //编写一个类 Operation 可以返回一个运算符 对应的优先级
    static class Operation {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;

        public static int getOperation(String s) {
            if (s.equals("+") || s.equals("-")) {
                return ADD;
            } else if (s.equals("/") || s.equals("*")) {
                return MUL;
            } else {
                System.out.println("输入有误:"+s);
                return -1;
            }
        }
    }
}

//    public static List<String> getListString(String suffixExpression){
//        String[] split = suffixExpression.split(" ");
//        List<String> list = new ArrayList<>();
//        for (String ele:split){
//            list.add(ele);
//        }
//        return list;
//    }
//
//    public static int calculate(List<String> ls){
//        Stack<String> stack = new Stack<String>();
//        for (String item:ls){
//            if (item.matches("\\d+")){
//                stack.push(item);
//            }else {
//                int num2 = Integer.parseInt(stack.pop());
//                int num1 = Integer.parseInt(stack.pop());
//                int res = 0;
//                if (item.equals("+")){
//                    res = num1 + num2;
//
//                }else if (item.equals("-")){
//                    res = num1 - num2;
//
//                }else if (item.equals("x")){
//                    res = num1 * num2;
//
//                }else if (item.equals("/")){
//                    res = num1 / num2;
//
//                }else {
////                    return Integer.parseInt(stack.pop());
//                    throw new RuntimeException();
//                }
//                stack.push(""+res);
//            }
//        }
//        return Integer.parseInt(stack.pop());
//    }

